//https://leetcode.cn/problems/extra-characters-in-a-string/?envType=daily-question&envId=2024-01-09



class Solution {
public:
    int minExtraChar(string s, vector<string> &dictionary) {
        unordered_set<string> set(dictionary.begin(), dictionary.end());
        int n = s.size();
        vector<int> f(n + 1);
        for (int i = 0; i < n; i++) 
        {
            f[i + 1] = f[i] + 1; // 不选
            for (int j = 0; j <= i; j++) // 枚举选哪个
                if (set.count(s.substr(j, i - j + 1))) f[i + 1] = min(f[i + 1], f[j]);
        }
        return f[n];
    }
};
